import java.util.Scanner;

public class QuickSort {
    //快速排序：以一个数为基数，把数组分成两部分，左边的数比基数小，右边的数比基数大，再把左右两边的数按
    // 这种方式排序，直到数组全部排序完毕。
    public static int onceTraversal(int[] a, int left, int right) {
        //以数组第一个为基数，
        //left为最左边的索引，right为最右边的索引
        int standard = a[left];// 以数组左边第一个元素为基数
        while (left < right) {
            //把a[left]看成一个坑位，从数组右边找一个比基数小的数，填到坑位
            while (a[right] > standard&&left<right) {
                right--;
            }
            if (left==right) {
                break;
            }
            //填坑,同时左边指针向右移动一格
            a[left] = a[right];
            left++;
            //这时把a[right]看成一个坑位，从数组左边边找一个比基数小的数，填到坑位
            while (a[left] < standard&&left<right) {
                left++;
            }
            if (left==right) {
                break;
            }
            //填坑,同时right向左移动一格
            a[right]=a[left];
            right--;
        }
        //把基数填到剩下的坑位
        a[left]=standard;
        return left;
    }
    public static void quickSort(int[] a, int left, int right) {
        //通过递归的方法,以middle为中间数把数组分成左右两部分，两边再分别排序，知道left=right
        if (left <right) {
            int middle = onceTraversal(a, left, right);
            quickSort(a, left, middle - 1);
            quickSort(a, middle + 1, right);
        }
    }

    public static void main(String[] args) {
        //用户输入一个数确定数组大小
        Scanner scanner = new Scanner(System.in);
        System.out.println("Please enter a interge to ensure the large of array:");
        //产生随机数
        int large = scanner.nextInt();
        scanner.close();
        int[] a = new int[large];
        int i;
        //打印长度为large的随机数组
        for (i = 0; i < a.length; i++) {
            a[i] = (int) (100 * Math.random());
            System.out.print(a[i] + " ");
        }
        System.out.println();
        System.out.println("\nAfter reoder ,the result of array is:");
        //调用quickSort方法
        quickSort(a, 0, a.length-1);
        //打印排序好的数组
        for (i = 0; i < a.length; i++) {
            System.out.print(a[i] + " ");
        }

    }
}
